package com.wangp.mywrite.coding;

import org.springframework.scheduling.annotation.Scheduled;

import java.util.*;

/**
 * @author: wp
 * @date: 2023/5/19 15:43:30
 * @desc:
 **/
public class CombinationSum3 {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        dfs(res, path, k, n, 1, 0);
        return res;
    }

    private void dfs(List<List<Integer>> res, LinkedList<Integer> path, int k, int n, int index, int sum) {
        if (path.size() == k) {
            if (sum == n) {
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = index; i <= 9 - (k - path.size()) + 1; i++) {
            path.add(i);
            sum += i;
            dfs(res, path, k, n, i + 1, sum);
            sum -= i;
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        System.out.println(new CombinationSum3().combinationSum3(2, 18));
    }
}
